Make your own free website on Tripod.com

Cooperative Multitasking for Quartus Forth

Copyright © 2001 Kristopher D. Johnson. All Rights Reserved.

Contents

Introduction

This document presents a set of cooperative multitasking extensions for the Quartus Forth development system.

These extensions allow application developers to organize an application as a set of tasks, each of which has its own data stack, return stack, and task-specific "user data" storage area. Tasks are scheduled in a round-robin fashion. Context switches occur under explicit control of the programmer.

There is no standard Forth wordset for multitasking. These extensions are patterned after descriptions of multitasking extensions provided by pbForth and by FORTH, Inc.'s products. However, the author has not used or examined either of those other products, and makes no claims about portability or semantic equivalence.

These extensions have been designed for and tested with Quartus Forth version 1.2.6R. The author believes that they will work with other 1.2.x versions of Quartus Forth, but has not tested them. Compatibility with future releases is not guaranteed.

Neal Bridges has indicated that he may add multitasking capabilities to the Quartus Forth kernel, so everything here may be obsolete in the near future. But it was an interesting problem to solve, and others may be interested in the techniques. It can be used as a base for more sophisticated multitasking systems or other alternate control structures.

The author invites comments and suggestions: kristopher_d_johnson@yahoo.com.

License

Copyright © 2001 Kristopher D. Johnson

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Source Files

The source files can be downloaded as a Zip file: mtask.zip

These files contain the cooperative multitasking word definitions.
coop.txt Defines INIT-TASKS, TASK, BUILD, ACTIVATE, PAUSE, SLEEP, AWAKE, NOD, HALT, and USER. Needs coop-tcb.txt, coop-operator.txt and coop-impl.txt.
coop-impl.txt Low-level implementation definitions. Application programmers should not use the words defined in this file. Needs coop-tcb.txt.
coop-tcb.txt Task Control Block structure definition.
coop-operator.txt Definition of the OPERATOR task.

These files contain demonstration applications and related utilities.
coop-debug.txt Implementations of words helpful in debugging tasks.
coop-demo.txt Simple cooperative multitasking demo. One task prints out values of the Fibonacci sequence while another prints the current system time once per second.
coop-test.txt Performance test that measures how long it takes to call the PAUSE word 100,000 times.
snowflakes.txt Demo that displays a set of fluttering snowflakes. Each snowflake is animated by a task.
snowflakes-make.txt Script for building standalone Snowflakes application.

The following optional files provide a more-efficient implementation of the FIELD word provided by the Quartus struct module. To use them, uncomment the "needs fastfield" line in coop-tcb.txt. Context switching is about 30% faster with this implementation of FIELD.
fastfield.txt Redefinition of FIELD. Needs m68k-addsub.txt.
m68k-addsub.txt Provides access to the M68000 ADDI and ADDQ instructions.

Word Descriptions

In the stack effect descriptions, "&task" is the address of a task control block. "<name>" is a space-delimited word that follows the described word.

INIT-COOP ( -- )

Initializes the global variables used by these extensions, and initializes the OPERATOR task. This word must be called before any other multitasking words are used.

(By the way, "COOP" rhymes with "NOOP", not with "LOOP".)

THIS-TASK ( -- &task )

Returns the address of the task control block for the currently executing task.

OPERATOR ( -- &task )

Returns the address of the OPERATOR task, which is the initial task created at program startup.

The OPERATOR task has some special characteristics associated with it--see the Limitations and Caveats section of this document for details.

TASK ( nUser nDataStack nReturnStack <name> -- )

Allocate a task control block in the dictionary for a task with the given number of bytes for the user data area, the data stack, and the return stack. The constants #task-user, #task-ds, and #task-rs can be used as reasonable values for the sizes.

At run-time, use of name will give the address of the Task Control Block. The expression "name @" will give the address of the task's user data area.

BUILD ( &task -- )

Initialize the task's return and data stacks, and link it into the task list. BUILD must be called at run-time, and must be called before the task is ACTIVATEd.

Results are undefined if BUILD is called more than once for a given task.

ACTIVATE ( &task -- )

Force the given task to start executing the words following the word ACTIVATE. The given task will not actually start executing words until it gets its turn in the round-robin rotation. The current task will treat ACTIVATE as an EXIT, returning to the definition that called the definition containing the ACTIVATE.

Results are undefined if an attempt is made to ACTIVATE a task before BUILD has been called for it.

It is legal to call ACTIVATE for a task that is already running. This will cause that task to stop whatever it was doing, reset its data and return stacks, and start executing the following words. An exception is an attempt to ACTIVATE the currently running task--in this case, ACTIVATE does nothing, and simply allows the task to continue executing the following words.

It is illegal to ACTIVATE the OPERATOR task. An attempt to do so will cause ABORT" to be called.

PAUSE ( -- )

Relinquishes the processor, allowing the next task to run.

SLEEP ( &task -- )

Puts the given task into "suspend mode", preventing it from running until AWAKE is called for the same task.

If SLEEP is called for the currently executing task, it will continue to run until PAUSE is called.

AWAKE ( &task -- )

Undoes the effect of SLEEP.

USER ( n <name> -- )

Defines a user area variable at the given offset from the start of a task's user data area. Use of name will give the address of the user variable; the phrases "name @" and "name !" can be used to fetch from or store to the variable.

NOD ( -- )

Puts current task into an endless loop that simply calls PAUSE over and over.

Tasks can use this word when they are "finished" with work, and waiting to be re-ACTIVATEd.

HALT ( &task -- )

Force the given task to call NOD. Equivalent to "ACTIVATE NOD".

Limitations and Caveats

This implementation is dependent upon undocumented and unsupported features specific to Quartus Forth's current implementation. These definitions will not work with other Forth implementations, and may fail with future versions of Quartus Forth.

This is cooperative multitasking, not preemptive multitasking. It is the programmer's responsibility to call PAUSE periodically within each task to allow context switching.

Palm OS is fundamentally a single-task system. The Palm OS doesn't know anything about cooperative multitasking. There is no way to run multiple applications simultaneously, nor to call multiple Palm OS API functions concurrently.

Multiple tasks are much more difficult to debug than single-task applications. Consider testing each of your tasks in isolation before putting them together. (And keep an unfolded paper clip handy!)

It advisable to ensure that at least one task contains a wait/timeout function (EKEY, (ekey), MS, etc.), as constant CPU usage will quickly drain a PDA's battery.

The only things saved and restored for tasks are the data stack, the return stack, and the user data area pointer. The CPU registers, global variables, and other parts of the machine state are not saved across context switches.

The user data areas for tasks use dictionary data space. Data stacks and return stacks are allocated from the Palm OS heap. The extensions themselves do not use any of the user data area, but do make use of the data and return stacks, so be sure to allocate plenty of space for those. (And remember that Palm OS and other Quartus Forth words use stack space as well.) Stack overflows and underflows are not checked. It is the programmer's responsibility to ensure that tasks' stacks are large enough. It is recommended to allocate 2K for the data stack and 1K for the return stack.

Once a task is BUILDt or ACTIVATEd, there is no way to "unbuild" it or "unactivate" it. In other words, there is no way to remove a task from the task list or to reclaim the memory allocated for its stacks.

If SLEEP is called for all tasks, then the scheduler will go into an endless loop. Don't do this.

ACTIVATE, PAUSE, and HALT can only be used within a compiled definition. Using these words interactively leads to undefined results.

Built-in Quartus Forth words that need to be aware of the "bottom" of the stack will only work within the OPERATOR task. Examples are DEPTH and .S. Tasks other than the OPERATOR task cannot be debugged interactively from the Quartus Forth console. This is because the Quartus Forth console event loop checks for stack underflow, and aborts whenever a secondary task's stack is the current stack.

It is illegal to ACTIVATE the OPERATOR task. The program will abort if this is attempted.

The exception stack is not saved or restored by context switches. This means that, in general, exceptions cannot be thrown or caught across tasks, or across invocations of the same task. In other words, a thrown exception must be caught within the same task, and PAUSE cannot be called between CATCH and THROW. However, these rules can be relaxed if you only use exceptions within a single task (only within the OPERATOR task, for example).

These extensions do not redefine any existing Quartus Forth words to be "task-aware", so don't expect any magical intelligent behavior. For example, calling MS will cause the entire program to be suspended; it will not simply suspend the current task and allow other tasks to proceed. Similarly, global variables and other global state continue to be global, and are not maintained on a task-by-task basis.

This implementation is focused on simplicity, not efficiency. Performance could be improved by reimplementing a few words in assembly code. But the author has no plans to do that.

How Does It Work?

This section describes how the COOP words do their thing. It only covers the "funky" parts of the implementation that may not be obvious. Interested readers are encouraged to study the word definitions themselves to learn all the details. The intended audience for this section is people who know Forth and understand a bit about how a CPU works, but who may not have experience with multitasking kernel implementations.

The real key to enlightenment is to understand how the PAUSE definition works. But first, we'll cover how Quartus Forth's stacks are implemented, and what a task control block looks like.

Stacks in Quartus Forth

This section assumes a little bit of knowledge about how the Motorola M68000 Family processors work. In summary, the CPU has a program counter (PC), which contains the location of the next instruction to be executed, eight data registers (D0-D7), and eight address registers (A0-A7). The processor supports 16-bit and 32-bit operations, and uses a 32-bit address representation.

Quartus Forth's data and return stacks both work on the same basic principle: a stack is an area of memory, and a CPU register contains the address of the "top" of the stack. The data stack pointer is held in the A4 register, and the return stack pointer is held in the A7 register. A4 and A7 contain double-cell absolute addresses, not single-cell relative addresses as are generally used for Quartus Forth programming.

To implement cooperative multitasking, we need to be able to save and restore the values of the two stack pointer registers when we switch between tasks. Most high-level languages do not provide direct access to stack pointers or machine registers, so manipulating them requires use of assembly language. But Quartus Forth provides the words SP@, SP!, RP@, and RP! to access the stack pointers, so we can define cooperative multitasking words without use of assembly language. (Thanks, Neal!)

Stacks grow downward in memory. When a cell (or double-cell) is pushed onto a stack, the stack pointer is decremented by two (or four) bytes, and then the value is stored to the new stack pointer location. When a cell is popped from the stack, the value is read from the current stack pointer location and then the stack pointer is incremented. The CPU has predecrement and postincrement addressing modes that make these operations fast.

The data stack is a little different in that the top cell of the stack is actually kept in the low 16-bits of the D7 register. This is an optimization technique: keeping the top of stack in a CPU register allows for some operations to be faster than if the top of stack were in memory. When you push a value to the data stack, the current value of the D7 register is pushed into the A4 memory area, and then D7 is loaded with the new value. When you pop a value, the value at the top of the A4 memory stack is moved into D7 and then the stack pointer is incremented. Quartus Forth's words take care of this automatically, so we don't really need to worry about it. The SP@ and SP! words take care of saving and restoring the contents of D7.

The return stack is used to hold PC return locations for subroutine calls. The locations on the return stack are all 32-bit (double-cell) values. The A7 register is special in that the CPU has instructions for using it implicitly as a return-stack pointer. (Note: A7 is referred to as "the SP" in M68xxx assembly language, but don't confuse that with the Forth data stack pointer.) When your program uses a Forth word, it executes the CPU's "Jump to Subroutine" (JSR) instruction, which pushes the current PC value to the A7 stack, and then loads the PC with the location of the code for that word. When a word definition exits, it uses the "Return from Subroutine" (RTS) instruction, which pops a location from the A7 stack and loads the PC with that location, which is generally the address following the JSR instruction that invoked the word.

Task Control Blocks, TASK, and BUILD

A task control block (TCB) is defined in the dictionary for each task. The TCBs are kept in a circular doubly-linked list so that the scheduler can cycle between them and so that new TCBs can be linked into the list. A TCB contains the following data elements:

When TASK is used to define a task, a TCB is ALLOTed, the desired sizes of the data stack and return stack are stored in the TCB, a user data area is ALLOTed, and the user data area address is stored in the first cell of the TCB.

When BUILD is used at run-time, it allocates memory from the Palm OS-managed heap for the data and return stacks, and stores those addresses in the TCB. (Note: the addresses of the upper end of the allocated areas are stored, as the stacks will grow downward from those addresses.) Then, it adds the TCB to the linked list; the new task is linked into the circular list at the position just before the currently running task. The TCB's state is marked as "skip", meaning that although this task is in the list, it is not yet ready to run.

The task list initially contains only the OPERATOR task. This task is linked to itself until BUILD links in another task. Unlike other tasks, OPERATOR's return and data stack areas are not allocated from the Palm OS heap; the OPERATOR task uses the stack areas initially provided by the Quartus Forth kernel.

How PAUSE Works

Upon entry to PAUSE, the top of the return stack contains the PC location of the instruction following the higher-level word's use of PAUSE. If we can just save that location, as well as the current data stack pointer, then we can go off and do something else, and then later we can restore the pointers and use the RTS instruction to return to the saved PC location in the higher-level word.

So, to switch between tasks, we can to save the current task's return and data stack pointers somewhere, choose a new task to run, restore that new task's return and data stack pointers, and then use RTS to have the new task it go back to where it was. We assume that the new task's context was saved by a previous PAUSE, or was initialized by ACTIVATE.

PAUSE is implemented as three lower-level words: SAVE-CONTEXT, SCHEDULE-TASK, and RESTORE-CONTEXT. Let's go through each one in order.

SAVE-CONTEXT's definition is as follows:

: save-context ( -- i**x )
  rp@ sp@ 2dup this-task tcb>ctx 2!
; inline
      

We use RP@ to put the current return stack pointer onto the data stack. Then we use SP@ to put the data stack pointer on the stack, and then save that to the "context pointer" field of the current task's TCB. SAVE-CONTEXT does not clean up the stack after doing its thing, but that's okay because we're about to change the stack pointer.

Note that we make SAVE-CONTEXT an INLINE word. If we don't do that, and make SAVE-CONTEXT a called subroutine, then the return stack's top element would point back into PAUSE rather than into the definition that used PAUSE, and that's not what we want.

SCHEDULE-TASK simply walks through the task list until it finds a task that is not marked to be skipped. It leaves the address of the new task's TCB on the stack.

RESTORE-CONTEXT's definition is as follows:

: restore-context ( &task -- )
  dup set-current-task
  tcb>ctx 2@ sp! rp!
; inline
      

We first use the SET-CURRENT-TASK word, which sets the variable used by THIS-TASK. Then, we retrieve the saved context pointer from the TCB and reverse the effect of SAVE-CONTEXT by using SP! to restore the task's data stack pointer and then RP! to restore the task's return stack pointer. So, when PAUSE exits, the return stack will contain the address of the next instruction to be executed for the restored task. (And again, we make the definition INLINE to avoid complications related to the use of the return stack.)

How ACTIVATE Works

Now that we know how PAUSE works, we can consider how ACTIVATE sets up a new task for execution. Basically, we need to do two things:

  1. Set up the activated task's context so that it will behave properly when PAUSE restores it.
  2. Make the current task return to the word that called the word containing ACTIVATE.

Upon entry to ACTIVATE, the return stack has the PC location in the higher-level word that called ACTIVATE as the first element, and the PC location of the word that called that word as the second element. If we remove the top stack element, using 2r>, then returning from ACTIVATE will get us back to the word that called the word that called ACTIVATE. So we've handled item #2. We'll pass the popped return location and the task control block address to the low-level word FORK-TASK, which will take care of item #1.

FORK-TASK does the following:

  1. Set the activated task's state to "running".
  2. Store the PC return location at the top of the task's return stack area.
  3. Store a pointer to the return stack at the top of the task's data stack area.
  4. Store a pointer to the top of the data stack into the task's context pointer.

So, after these steps are complete, the "SP! RP!" sequence of RESTORE-CONTEXT within PAUSE will cause the forked task to continue by executing the words following ACTIVATE.


Author:

Kris Johnson
Last modified: Sat Jan 13 14:24:49 EST 2001